#include <vector>
#include <string>
#include <algorithm>
#include <climits>
#include <iostream>

using namespace std;

class Code04_DecodeWaysII
{
public:
    static const long mod = 1000000007;

    // 没有取模逻辑
    // 最自然的暴力尝试
    static int numDecodings1(string str)
    {
        return f1(str, 0);
    }

    // s[i....] 有多少种有效转化
    static int f1(const string &s, int i)
    {
        if (i == s.length())
        {
            return 1;
        }
        if (s[i] == '0')
        {
            return 0;
        }
        // s[i] != '0'
        // 2) i想单独转
        int ans = f1(s, i + 1) * (s[i] == '*' ? 9 : 1);
        // 3) i i+1 一起转化 <= 26
        if (i + 1 < s.length())
        {
            // 有i+1位置
            if (s[i] != '*')
            {
                if (s[i + 1] != '*')
                {
                    // num num
                    //  i  i+1
                    if ((s[i] - '0') * 10 + s[i + 1] - '0' <= 26)
                    {
                        ans += f1(s, i + 2);
                    }
                }
                else
                {
                    // num  *
                    //  i  i+1
                    if (s[i] == '1')
                    {
                        ans += f1(s, i + 2) * 9;
                    }
                    if (s[i] == '2')
                    {
                        ans += f1(s, i + 2) * 6;
                    }
                }
            }
            else
            {
                if (s[i + 1] != '*')
                {
                    // *  num
                    // i  i+1
                    if (s[i + 1] <= '6')
                    {
                        ans += f1(s, i + 2) * 2;
                    }
                    else
                    {
                        ans += f1(s, i + 2);
                    }
                }
                else
                {
                    // *  *
                    // i  i+1
                    // 11 12 ... 19 21 22 ... 26 -> 一共15种可能
                    // 没有10、20，因为*只能变1~9，并不包括0
                    ans += f1(s, i + 2) * 15;
                }
            }
        }
        return ans;
    }

    // 记忆化搜索
    static int numDecodings2(string str)
    {
        vector<long> dp(str.length(), -1);
        return (int)f2(str, 0, dp);
    }

    static long f2(const string &s, int i, vector<long> &dp)
    {
        if (i == s.length())
        {
            return 1;
        }
        if (s[i] == '0')
        {
            return 0;
        }
        if (dp[i] != -1)
        {
            return dp[i];
        }
        long ans = f2(s, i + 1, dp) * (s[i] == '*' ? 9 : 1);
        if (i + 1 < s.length())
        {
            if (s[i] != '*')
            {
                if (s[i + 1] != '*')
                {
                    if ((s[i] - '0') * 10 + s[i + 1] - '0' <= 26)
                    {
                        ans += f2(s, i + 2, dp);
                    }
                }
                else
                {
                    if (s[i] == '1')
                    {
                        ans += f2(s, i + 2, dp) * 9;
                    }
                    if (s[i] == '2')
                    {
                        ans += f2(s, i + 2, dp) * 6;
                    }
                }
            }
            else
            {
                if (s[i + 1] != '*')
                {
                    if (s[i + 1] <= '6')
                    {
                        ans += f2(s, i + 2, dp) * 2;
                    }
                    else
                    {
                        ans += f2(s, i + 2, dp);
                    }
                }
                else
                {
                    ans += f2(s, i + 2, dp) * 15;
                }
            }
        }
        ans %= mod;
        dp[i] = ans;
        return ans;
    }

    // 动态规划
    static int numDecodings3(string str)
    {
        int n = str.length();
        vector<long> dp(n + 1, 0);
        dp[n] = 1;
        for (int i = n - 1; i >= 0; i--)
        {
            if (str[i] != '0')
            {
                dp[i] = (str[i] == '*' ? 9 : 1) * dp[i + 1];
                if (i + 1 < n)
                {
                    if (str[i] != '*')
                    {
                        if (str[i + 1] != '*')
                        {
                            if ((str[i] - '0') * 10 + str[i + 1] - '0' <= 26)
                            {
                                dp[i] += dp[i + 2];
                            }
                        }
                        else
                        {
                            if (str[i] == '1')
                            {
                                dp[i] += dp[i + 2] * 9;
                            }
                            if (str[i] == '2')
                            {
                                dp[i] += dp[i + 2] * 6;
                            }
                        }
                    }
                    else
                    {
                        if (str[i + 1] != '*')
                        {
                            if (str[i + 1] <= '6')
                            {
                                dp[i] += dp[i + 2] * 2;
                            }
                            else
                            {
                                dp[i] += dp[i + 2];
                            }
                        }
                        else
                        {
                            dp[i] += dp[i + 2] * 15;
                        }
                    }
                }
                dp[i] %= mod;
            }
        }
        return (int)dp[0];
    }

    // 动态规划 + 空间压缩
    static int numDecodings4(string str)
    {
        int n = str.length();
        long cur = 0, next = 1, nextNext = 0;
        for (int i = n - 1; i >= 0; i--)
        {
            if (str[i] != '0')
            {
                cur = (str[i] == '*' ? 9 : 1) * next;
                if (i + 1 < n)
                {
                    if (str[i] != '*')
                    {
                        if (str[i + 1] != '*')
                        {
                            if ((str[i] - '0') * 10 + str[i + 1] - '0' <= 26)
                            {
                                cur += nextNext;
                            }
                        }
                        else
                        {
                            if (str[i] == '1')
                            {
                                cur += nextNext * 9;
                            }
                            if (str[i] == '2')
                            {
                                cur += nextNext * 6;
                            }
                        }
                    }
                    else
                    {
                        if (str[i + 1] != '*')
                        {
                            if (str[i + 1] <= '6')
                            {
                                cur += nextNext * 2;
                            }
                            else
                            {
                                cur += nextNext;
                            }
                        }
                        else
                        {
                            cur += nextNext * 15;
                        }
                    }
                }
                cur %= mod;
            }
            nextNext = next;
            next = cur;
            cur = 0;
        }
        return (int)next;
    }
};

int main()
{
    string s = "1*";

    int result1 = Code04_DecodeWaysII::numDecodings1(s);
    int result2 = Code04_DecodeWaysII::numDecodings2(s);
    int result3 = Code04_DecodeWaysII::numDecodings3(s);
    int result4 = Code04_DecodeWaysII::numDecodings4(s);

    // 输出结果
    cout << "Result 1: " << result1 << endl;
    cout << "Result 2: " << result2 << endl;
    cout << "Result 3: " << result3 << endl;
    cout << "Result 4: " << result4 << endl;

    return 0;
}
